package com.fosss.linkedList;

/**
 * 单项环形链表
 */
public class Josepfu {
    public static void main(String[] args) {
        CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
        circleSingleLinkedList.addBoy(5);
        circleSingleLinkedList.showBoys();
        System.out.println("--------------------------------");
        circleSingleLinkedList.game(1,2,5);
    }
}

//创建单向环形链表
class CircleSingleLinkedList{
    private Boy first=new Boy();
    public void addBoy(int nums){
        if (nums <= 0) {
            System.out.println("num的数据不正确");
            return;
        }
        Boy curBoy=null;//构建一个辅助指针,因为first不能动
        for(int i = 1;i<=nums; i++){
            Boy boy=new Boy(i);
            if(i==1){
                first=boy;
                first.setNext(first);//形成环形链表
                curBoy=first;
            }else {
                curBoy.setNext(boy);
                boy.setNext(first);
                curBoy=boy;
            }
        }
    }

    //遍历输出链表
    public void showBoys(){
        if(first==null){
            System.out.println("链表为空");
            return;
        }
        Boy boy=first;
        while (true){
            System.out.printf("小孩的编号为%d \n",boy.getNo());
            if(boy.getNext()==first){
                break;
            }
            boy=boy.getNext();
        }
    }



    /** 完成出圈效果
     *
     * @param startNo 表示从第几个小孩开始数
     * @param countNum 表示数几个数
     * @param nums 表示一共有几个小孩  这里的nums没有在方法中用到，可以将上边的添加方法合并到此方法中
     */
    public void game(int startNo,int countNum,int nums){
        //数据校验
        if(first==null||startNo>nums||nums<1|startNo<1||countNum < 1){
            System.out.println("数据不正确");
        }

        //创建辅助指针，实现指向链表的最后一个节点
        Boy helper=first;
        while (helper.getNext()!=first){
            helper=helper.getNext();
        }
        //当小孩报数时，让first和helper同时移动n-1次
        for(int i = 1; i < startNo; i++){
            first=first.getNext();
            helper=helper.getNext();
        }
        while (true){
            if(helper==first){
                //说明只剩一个节点
                break;
            }
            //移动到要出圈的小孩
            for(int i = 1; i < countNum; i++){
                first = first.getNext();
                helper = helper.getNext();
            }
            //将first指向的小孩出圈,原来first指向的节点由于没有任何引用，会被回收
            System.out.println("出圈的小孩编号依次为："+first.getNo()+" ");
            first=first.getNext();
            helper.setNext(first);
        }
        System.out.println("最后留在圈中的小孩编号为："+first.getNo());
    }
}

//创建小孩类
class Boy{
    public int no;
    private Boy next;//指向下一个小孩
    public Boy() {

    }
    public Boy(int no){
        this.no = no;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public Boy getNext() {
        return next;
    }

    public void setNext(Boy next) {
        this.next = next;
    }
}

























